package com.cong.leetcode._338;

//给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。
//
//        示例 1:
//
//        输入: 2
//        输出: [0,1,1]
//        示例 2:
//
//        输入: 5
//        输出: [0,1,1,2,1,2]
//
//        来源：力扣（LeetCode）
//        链接：https://leetcode-cn.com/problems/counting-bits
//        著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

// 我将在O(n) 时间完成该题
class Solution {
    public int[] countBits(int num) {
        if (num == 0) {
            return new int[] {0};
        }
        if (num == 1)
            return new int[] {0, 1};
        int[] res = new int[num + 1];
        res[0] = 0;
        res[1] = 1;
        int leftPointer = 0, rightPointer = 1, indexPointer = 2;
        while (indexPointer <= num) {
            res[indexPointer] = 1 + res[leftPointer];
            if (leftPointer == rightPointer) {
                rightPointer = indexPointer;
                leftPointer = 0;
                indexPointer++;
                continue;
            }
            indexPointer++;
            leftPointer++;
        }

        return res;
    }
}